// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 11:37
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class LowestCommonAncestorUpdate {
    /**
     * 保留一个节点的遍历序列，然后根据这个遍历序列对另一个节点进行搜寻
     * 两个节点的最近父节点为列表中的末尾节点
     */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path = new ArrayList<>();
        find(root, p, path);
        TreeNode ans = root;
        TreeNode next = root;
        while (!path.isEmpty()) {
            TreeNode node = path.remove(0);
            if (node.val == next.val) {
                // 要找的两个节点中有一个节点是另一个节点的父节点
                ans = node;
            }
            // 根据当前路径进行寻找
            if (q.val > next.val) {
                next = next.right;
            } else if (q.val < next.val) {
                next = next.left;
            }
        }
        return ans;
    }

    /**
     * 在给定树中存储访问指定节点的路径，存储路径列表t&&f
     *
     * @param root 根节点
     * @param p    查找节点+
     * @param list 记录路径的链表
     */
    private void find(TreeNode root, TreeNode p, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        if (root.val > p.val) {
            find(root.left, p, list);
        } else if (root.val < p.val) {
            find(root.right, p, list);
        }
    }


    @Test
    public void shout() {
        int[] nodes = {6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5};
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(new LowestCommonAncestorUpdate().lowestCommonAncestor(root, root.left, root.right));

    }
}
